﻿// 2513. 最小化两个数组中的最大值.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>

using namespace std;

/*
https://leetcode.cn/problems/minimize-the-maximum-of-two-arrays/description/

给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：

arr1 包含 uniqueCnt1 个 互不相同 的正整数，每个整数都 不能 被 divisor1 整除 。
arr2 包含 uniqueCnt2 个 互不相同 的正整数，每个整数都 不能 被 divisor2 整除 。
arr1 和 arr2 中的元素 互不相同 。
给你 divisor1 ，divisor2 ，uniqueCnt1 和 uniqueCnt2 ，请你返回两个数组中 最大元素 的 最小值 。


示例 1：
输入：divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
输出：4
解释：
我们可以把前 4 个自然数划分到 arr1 和 arr2 中。
arr1 = [1] 和 arr2 = [2,3,4] 。
可以看出两个数组都满足条件。
最大值是 4 ，所以返回 4 。

示例 2：
输入：divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
输出：3
解释：
arr1 = [1,2] 和 arr2 = [3] 满足所有条件。
最大值是 3 ，所以返回 3 。

示例 3：
输入：divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
输出：15
解释：
最终数组为 arr1 = [1,3,5,7,9,11,13,15] 和 arr2 = [2,6] 。
上述方案是满足所有条件的最优解。


提示：
2 <= divisor1, divisor2 <= 105
1 <= uniqueCnt1, uniqueCnt2 < 109
2 <= uniqueCnt1 + uniqueCnt2 <= 109
*/

class Solution {
public:
    int gcdv = -1;
    long long lcmv = -1;

    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    bool check(long long x, int diva, int divb, int cnt1, int cnt2) {
        long long cnt = 0;
        cnt += min(1LL * cnt1, x / divb - x / lcmv);
        cnt += min(1LL * cnt2, x / diva - x / lcmv);
        cnt += x - x / diva - x / divb + x / lcmv;

        if (cnt >= (cnt1 + cnt2)) return true;
        return false;
    }

    int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        long long l = uniqueCnt1 + uniqueCnt2; long long r = 90000000010;
        lcmv = 1LL * divisor1 * divisor2 / gcd(divisor1, divisor2);
        while (l < r) {
            long long mid = l + r >> 1;
            if (check(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2)) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }

        //处理l 只选最大值
        for (int i = l; i >= 1; i--) {
            if (i % divisor1 == 0 && i % divisor2 == 0) {
                continue;
            }
            else return i;
        }

        return -1;
    }
};


int main()
{
    Solution s;
    cout << s.minimizeSet(2557,15901, 805236426, 194763574) << endl;
}

 